package violentRecursion;

/**
 * @author kunkun
 * @className LeetCode_279
 * @Description 完全平方数
 * @date 2025/3/13 13:17
 */
public class LeetCode_279 {

    public int numSquares(int n) {
        return solution_1(n);
    }

    //暴力递归
    private int solution_1(int n) {
        //递归截至条件
        if (n==1){
            return 1;
        }
        int maxIndex = (int) Math.sqrt(n);
        if (n==maxIndex*maxIndex){
            return 1;
        }
        //递归循环
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= maxIndex; i++) {

            int value = 1+solution_1(n-i*i);
            if (min>value){
                min=value;
            }
        }
        return min;
    }

    //动态规划
    private int solution_2(int n){
        //1. 定义
        int[] results = new int[n+1];
        for (int i = 1; i <= (int)Math.sqrt(n) ; i++) {
            results[i]=1;
        }

        //2. for遍历
        for (int i = 2; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= (int)Math.sqrt(i); j++) {
                int value = 1+results[i-j*j];
                if (min>value){
                    min=value;
                }
            }
            results[i]=min;
        }
        return results[n];
    }


}
